package com.exercises;


import java.util.TreeSet;

class Exercise363 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 2};
        int k = 4, result = Integer.MIN_VALUE;
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(0);
        int sum = 0;
        for (int eachRow : arr) {
            sum += eachRow;
            Integer ceil = treeSet.ceiling(sum - k);
            if (ceil != null) {
                result = Math.max(result, sum - ceil);
            }
            treeSet.add(sum);
        }
    }


    public int maxSumSubmatrix(int[][] matrix, int k) {
        int result = Integer.MIN_VALUE;
        int m = matrix.length, n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            int rowSum[] = new int[n];
            for (int j = i; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    rowSum[l] += matrix[j][l];
                }
                TreeSet<Integer> treeSet = new TreeSet<>();
                treeSet.add(0);
                int sum = 0;
                for (int eachRow : rowSum) {
                    sum += eachRow;
                    Integer ceil = treeSet.ceiling(sum - k);
                    if (ceil != null) {
                        result = Math.max(result, sum - ceil);
                    }
                    treeSet.add(sum);
                }
            }
        }
        return result;
    }


}

